% We need to:
% Show that cloning can lead to less code expansion than inlining.
% Show that there are recursive functions that would benefit from cloning.
% Find actual performance bugs in SPEC CPU 2006
% Test our optimizations in programs that are not benchmarks, where we can have
%   more opportunities to do well.
% Perhaps think about other clone based optimizations

\documentclass[10pt]{cgo13}

\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{skak}
\usepackage{pbox}

\newtheorem{definition}[section]{Definition}

% Definition of new commands that I use in this text:
\newcommand{\fun}[1]{\mbox{\textbf{#1}}}
\newcommand{\lb}[1]{#1_{\downarrow}}
\newcommand{\ub}[1]{#1_{\uparrow}}
\newcommand{\varset}[1]{\mbox{$\cal{#1}$}}
\newcommand{\code}[1]{\textbf{#1}}

\setlength{\textfloatsep}{12.0pt plus 1.0pt minus 1.0pt}

\begin{document}

\conferenceinfo{CGO '14}{23-27 February 2013, Shenzhen China.}
\copyrightyear{2014}
\copyrightdata{978-1-4673-5525-4/13/\$31.00 \copyright2013 IEEE}

\titlebanner{Dynamic Trip Count Prediction}        % These are ignored unless
\preprintfooter{Loop Prediction}   % 'preprint' option specified.

\title{Dynamic Trip Count Prediction}
%\subtitle{A case study of the Dinamica EGO toolkit}

\authorinfo{Author Names Removed Due to Blind Review}

%\authorinfo{Matheus Silva Vilela, Guilherme Balena Versiani,
%Fernando Magno Quint\~{a}o Pereira}
%{Department of Computer Science -- The Federal University of Minas Gerais (UFMG) -- Brazil}
%{\{matheusv,guibv,fernando\}@dcc.ufmg.br}

\maketitle

\begin{abstract}
% Context
The number of iterations that a loop performs is determined by its
{\em trip count}.
Several compiler optimizations yield greater benefit for large trip counts,
and are either innocuous or detrimental for small ones.
% Problem
However, predicting exactly the size of a trip count is an undecidable problem.
Thus, usually compilers generate code to handle the large and small cases in
the same way.
% Solution
In this paper we present a simple heuristic to predict the size of trip
counts, and discuss different ways to capitalize on this information.
Firstly, we show how this predictor helps us to speed up the execution of
JavaScript programs in the firefox browser, a highly tuned environment.
Secondly, we show how our idea lets us implement a memory controller
that places data more efficiently in a Numa-based multi-core architecture.
% Results
Even though our heuristic is remarkably simple - it has zero-overhead in
practice - it yields very accurate results.
We have been able to predict exactly over 60\% off all the loops found in
hundreds of JavaScript actual pages, and in millions of lines of C code.
Our modified firefox is 1-5\% faster than the original implementation, and
our memory controller has been able to speed up linear algebra applications by
up to XX\%.
\end{abstract}

\category{D.3.4}{Processors}{Compilers}

\terms
Languages, Performance

\keywords
Just-in-time Compilation, Loop analysis, JavaScript

\section{Introduction}
\label{sec:int}

% The importance of loops
A well-known maxim in the compiler community states that ``all the gold lays
in the loops".
Loops account for most of the execution time of a program, and usually
compilers go to long extents to generate efficient code for them.
There exists, indeed, a vast literature that deals specifically with loop
optimizations~\cite{Kennedy02,Wolfe96}.
Most of these optimizations usually pay different dividends, depending on
how many iterations the target loop executes.
The return they deliver for fast loops, which execute only a few iterations, is
usually much smaller than the reward they yield for the long loops.
Henceforth, we shall call the number of iterations that a loop performs during
one of its executions its {\em trip count}.
This is a dynamic notion: we know the exact trip count of a loop once the
program flow leaves it.
If the compiler had a way to know the trip count of a loop before executing it,
then it could choose the most appropriate code for a small or large number of
iterations dynamically.

% Why predicting accurately at low cost is hard.
Nevertheless, just like any other interesting property of a program, Rice's
Theorem~\cite{RiceXX} tells us that predicting this quantity is an undecidable
program.
Therefore, a predictor must work with heuristics.
The literature contains a few works, on the lines of adaptive compilation, that
generates different code based on different characteristics of the input that
a program receives~\cite{Tian10,Tian11,Samadi12}.
Runtime characteristics of the particular input determine which routine will be
activated.
In our opinion, these works have two shortcomings.
First, their granularity is to coarse: they deal with either functions, or the
entire program.
We believe that much can be obtained from looking at loops individually.
Second, these heuristics, although very precise, are too heavy to be used, for
instance, in the lightweighted environment of a just-in-time compiler. 

% What we have done: the simple heuristics

% How we have used it: jit and numa

% a Summary of our results.

\section{Background}
\label{sec:bkg}


\section{Trip Count Prediction}
\label{sec:sol}


\subsection{Use in Just-in-time Compilation}
\label{sub:jit}


\subsection{Use in Memory Controller}
\label{sub:numa}


\section{Experimental Results}
\label{sec:exp}


\section{Related Works}
\label{sec:rel}


\section{Conclusion}
\label{sec:con}


\bibliographystyle{plain}
\bibliography{../references}

\end{document}
